package ru.eas;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

/**
 * @author aesipov
 */
public class IntervalTree {

    public static void main(String[] args) {
//        String testString = "14 13\n" +
//                "0 12\n" +
//                "5 7\n" +
//                "0 6 " +
//                "6 12 " +
//                "3 7 " +
//                "5 9 " +
//                "2 5 " +
//                "7 10 " +
//                "1 2 " +
//                "3 4 " +
//                "5 6 " +
//                "7 8 " +
//                "9 10 " +
//                "11 12 " +
//                "0 1 2 3 4 5 6 7 8 9 10 11 12";
//        Scanner scanner = new Scanner(testString);
//
////        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int m = scanner.nextInt();
//        Interval[] intervals = new Interval[n];
//        for (int i = 0; i < n; i++) {
//            intervals[i] = new Interval(scanner.nextInt(), scanner.nextInt());
//        }
//        int[] points = new int[m];
//        for (int i = 0; i < m; i++) {
//            points[i] = scanner.nextInt();
//        }

        Interval[] intervals = generateIntervals().toArray(new Interval[0]);
        int[] points = generatePoints();

        long p1 = System.currentTimeMillis();

        IntervalTree intervalTree = new IntervalTree(intervals);

        long p2 = System.currentTimeMillis();
        System.out.println(p2 - p1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < points.length; i++) {
            sb.append(intervalTree.getIntervalCount(points[i]));
            sb.append(" ");
        }
        System.out.println(sb.toString());

        long p3 = System.currentTimeMillis();
        System.out.println(p3 - p2);
    }

    private static int[] generatePoints() {
        Random random = new Random();
        int[] result = new int[50000];
        for (int i = 0; i < result.length; i++) {
            result[i] = random.nextInt() % 100000;
        }
        return result;
    }

    private static List<Interval> generateIntervals() {
        Random random = new Random();
        List<Interval> result = new ArrayList<Interval>();
        for (int i = 0; i < 50000; i++) {
            int left = random.nextInt() % 100000;
            int right = random.nextInt() % 100000;
            if (left <= right) {
                result.add(new Interval(left, right));
            } else {
                result.add(new Interval(right, left));
            }
        }
        return result;
    }

    private Node root;
    private MedianFinder medianFinder = new MedianFinder();

    public IntervalTree(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval i1, Interval i2) {
                return (i1.left < i2.left) ? -1 : ((i1.left == i2.left) ? 0 : 1);
            }
        });
        root = createNode(intervals);
    }

    private Node createNode(Interval[] intervals) {
        if (intervals.length == 0) {
            return null;
        }
        int median = findMedian(intervals);
        List<Interval> centerOrderedByLeft = new ArrayList<Interval>();
        List<Interval> left = new ArrayList<Interval>();
        List<Interval> right = new ArrayList<Interval>();
        for (int i = 0; i < intervals.length; i++) {
            Interval interval = intervals[i];
            if (interval.left > median ) {
                right.add(interval);
            } else if (interval.right >= median) {
                centerOrderedByLeft.add(interval);
            } else {
                left.add(interval);
            }
        }
        List<Interval> centerOrderedByRight = new ArrayList<Interval>(centerOrderedByLeft);
        Collections.sort(centerOrderedByRight, new Comparator<Interval>() {
            @Override
            public int compare(Interval i1, Interval i2) {
                return (i2.right < i1.right) ? -1 : ((i2.right == i1.right) ? 0 : 1);
            }
        });
        Node leftNode = createNode(left.toArray(new Interval[left.size()]));
        Node rightNode = createNode(right.toArray(new Interval[right.size()]));
        return new Node(median, centerOrderedByLeft, centerOrderedByRight, leftNode, rightNode);
    }

    private int findMedian(Interval[] intervals) {
        int size = intervals.length;
        int[] array = new int[size * 2];
        for (int i = 0; i < size; i++) {
            array[i] = intervals[i].left;
        }
        for (int i = 0; i < size; i++) {
            array[size + i] = intervals[i].left;
        }
        return medianFinder.median(array, 0, array.length - 1, array.length / 2);
    }

    public int getIntervalCount(int point) {
        return getIntervalCount(root, point);
    }

    public int getIntervalCount(Node node, int point) {
        if (node == null) {
            return 0;
        }
        if (point == node.median) {
            return node.leftBounds.length;
        }
        if (point < node.median) {
            int index = searchKeyOrLessForIncreaseSort(node.leftBounds, point, 0, node.leftBounds.length - 1);
            return index + 1 + getIntervalCount(node.left, point);
        } else {
            int index = searchKeyOrGreatForDecreaseSort(node.rightBounds, point, 0, node.rightBounds.length - 1);
            return index + 1 + getIntervalCount(node.right, point);
        }
    }

    public int searchKeyOrLessForIncreaseSort(int[] array, int key, int left, int right) {
        while (left <= right) {
            int middle = (right + left) / 2;
            if (array[middle] == key) {
                return middle;
            }
            if (key < array[middle]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return right;
    }

    public int searchKeyOrGreatForDecreaseSort(int[] array, int key, int left, int right) {
        while (left <= right) {
            int middle = (right + left) / 2;
            if (array[middle] == key) {
                return middle;
            }
            if (key < array[middle]) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return right;
    }


    class MedianFinder {
        private Random random = new Random();

        public int median(int[] array, int left, int right, int k) {
            while (left <= right) {
                int pivot = partition(array, left, right);

                if (k == pivot) {
                    return array[pivot];
                }
                if (k < pivot) {
                    right = pivot - 1;
                } else {
                    left = pivot + 1;
                }
            }
            return left;
        }

        private int partition(int[] array, int left, int right) {
            if (left < right) {
                swap(array, random.nextInt(right - left) + left, left);
            }
            int l = left;
            int pivot = array[left];
            for (int r = left + 1; r <= right; r++) {
                int key = array[r];
                if (key <= pivot) {
                    l++;
                    swap(array, l, r);
                }
            }
            swap(array, left, l);
            return l;
        }

        private void swap(int[] array, int l, int r) {
            int tmp = array[l];
            array[l] = array[r];
            array[r] = tmp;
        }
    }

    static class Interval {
        int left;
        int right;

        Interval(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "[" + left +
                    ", " + right +
                    ']';
        }
    }

    class Node {
        int median;
        int[] leftBounds;
        int[] rightBounds;
        Node left;
        Node right;

        Node(int median, List<Interval> intervalsOrderedByLeft, List<Interval> intervalsOrderedByRight, Node left, Node right) {
            this.median = median;
            this.left = left;
            this.right = right;

            leftBounds = new int[intervalsOrderedByLeft.size()];
            for (int i = 0; i < leftBounds.length; i++) {
                leftBounds[i] = intervalsOrderedByLeft.get(i).left;
            }
            rightBounds = new int[intervalsOrderedByRight.size()];
            for (int i = 0; i < rightBounds.length; i++) {
                rightBounds[i] = intervalsOrderedByRight.get(i).right;
            }
        }
    }
}
